package fun.coding.recursion;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;

public class RecursionImpl implements Recursion {

    @Override
    public ArrayList<String[]> solveNQueens(int n) {
        
        int[] q = new int[n];
        ArrayList<String[]> res = new ArrayList<String[]>();
        
        place(q, 0, res);
        
        return res;
    }

    private void place(int[] q, int qNum, ArrayList<String[]> res) {
        if(qNum == q.length) {
            printSolution(q, res);
        } else {
            for(int i = 0; i < q.length; ++i) {
                q[qNum] = i;
                if(canPlace(q, qNum)) {
                    place(q, qNum + 1, res);
                }
            }    
        }
    }
    
    private boolean canPlace(int[] q, int qNum) {
        for(int i = 0; i < qNum; ++i) {
            // check the column and diagonals. Imagine a square thing for diagonals. 
            if(q[i] == q[qNum] || Math.abs(q[i] - q[qNum]) == qNum - i) {
                return false;
            }
        }
        
        return true;
    }
    
    private void printSolution(int[] q, ArrayList<String[]> res) {
        String[] s = new String[q.length];
        
        for(int i = 0; i < q.length; ++i) {
            StringBuilder sb = new StringBuilder();
            for(int j = 0; j < q.length; ++j) {
                if(q[i] == j) {
                    sb.append("Q");
                } else {
                    sb.append(".");    
                }
                
            }
            s[i] = sb.toString();
        }
        
        res.add(s);
    }

    /*
     * Permutate the string. 
     * s = "abc"
		output = {abc, acb, bac, bca, cab, cba}
		for example, 
		c 
		cb, bc
		acb, cab, cba, abc, bac, bca
     * 
     */
    @Override
    public ArrayList<String> getPermutations(String str) {
        
        ArrayList<String> res = new ArrayList<String>();
        
        if(str.length() == 0) {
        //if(StringUtils.isEmpty(str)) {
            res.add("");
            return res;
        }
        
        char first = str.charAt(0);
        String remainder = str.substring(1);
        ArrayList<String> partial = getPermutations(remainder);
        
        for(String s : partial) {
            for(int i = 0; i <= s.length(); ++i) {
                String ss = insertStringAtIndex(s, i, first);
                res.add(ss);
            }
            
        }
        return res;
    }
    
    private String insertStringAtIndex(String s, int i, char c) {
        String start = s.substring(0, i);
        String end = s.substring(i);
        return start + c + end;
    }
    
    @Override
    public void getPermutation(String str) {
        getPermuationHelper("", str);
    }

    // This is from one of the interviee's for Amazon. 
    private static void getPermuationHelper(String first, String rest)
    {
        int n = rest.length();

        if(n == 0)
        {
            System.out.println(first);
        } else
        {
            for(int i=0;i<n;i++)
            {
                getPermuationHelper(first+rest.charAt(i),rest.substring(i+1,n)+rest.substring(0,i));
            }

        }
    }
    

    /* My facebook onsite interview.
     * n = 5, 
     * a = {1, 2, 3, 4, 5}
     * k = 2
     * 1, 2; 1, 3; 1, 4; 1,5;2,3;2,4;2,5;3,4;3,5;4,5;
     * Got asked the same question by Microsoft again. But microsoft one is about the whole subset, in that case, use 2^n. 
     * 
     * http://stackoverflow.com/questions/4555565/generate-all-subsets-of-size-k-from-a-set
     * recursion is my friend!
     * */
    @Override
    public void printKSubset(int n, int k) {
        int[] array = new int[n];
        for(int i = 0; i < n; ++i) {
            array[i] = i + 1;
        }
        ArrayList<Integer> list = new ArrayList<Integer>();
        
        printKSubsetHelper(array, n, k, 0, list);
        
    }
    
    public void printKSubsetHelper(int[] array, int n, int length, int index, ArrayList<Integer> list) {
        if(length == 0) {
            System.out.println(Arrays.asList(list));
            return;
        }
        
        for(int i = index; i < n; ++i) {
            list.add(array[i]);
            printKSubsetHelper(array, n, length - 1, i + 1, list);
            list.remove(list.size() - 1);
        }
    }

    /* there could be potentially many paths. 
     * 
     *  000 0
     *  001 1
     *  011 3
     *  010 2
     *  110 6
     *  111 7
     *  101 5
     *  100 4
     * 
     * There is a very easy way without recursion. 
     * http://blog.csdn.net/zhiyu27/article/details/8191544
     * 
     * */
    @Override
    public ArrayList<Integer> grayCode(int n) {
        if(n == 0) {
            ArrayList<Integer> a = new ArrayList<Integer>();
            a.add(0);
            return a;
        }
        
        if(n == 1) {
            ArrayList<Integer> a = new ArrayList<Integer>();
            a.add(0);
            a.add(1);
            return a;
        }
        
        ArrayList<Integer> res = grayCode(n - 1);
        
        ArrayList<Integer> a = new ArrayList<Integer>();
        
        for(int i = 0; i < res.size(); ++i) {
            a.add(res.get(i));
        }
        
        int base = 1 << (n - 1);
        for(int i = res.size() - 1; i >= 0; --i) {
            a.add(base + res.get(i));
        }
        
        return a;
    }

    /** CC150 problem:
     * give infinite number of coins, 25 cents, 10 cents, 5 cents and 1 cent, 
     * calculate the number of ways to represent n cents. 
     */
    
    @Override
    public int numberOfWaysToMatchCoins(int money) {
        // TODO: should make this an input param
        return matchCoinsHelper(money, 25);
    }   
    
    private int matchCoinsHelper(int money, int denom) {
        int nextDenom = 0;
        
        switch (denom) {
        case 25:
            nextDenom = 10;
            break;
        case 10:
            nextDenom = 5;
            break;
        case 5:
            nextDenom = 1;
            break;
        case 1:
            return 1;
                
        }
        
        int ways = 0;
        
        for (int i = 0; i * denom <= money; i++) {
            ways += matchCoinsHelper(money - i * denom, nextDenom);
        }
        return ways;
    }
    
}
